﻿

namespace Graph.Algorithm.Core;


/// <summary>
/// 有向无权图 最短路
/// </summary>
public class UnweightedGraphShortestPath
{ 
    private List<Record> _records { get; set; } = new List<Record>();

    ///// <summary>
    ///// 所有路径长度
    ///// </summary>
    //public Dictionary<int, double> dists = new Dictionary<int, double>();
    ///// <summary>
    ///// 所有路径点位置   后面的为父级
    ///// </summary>
    //public Dictionary<int, int> paths = new Dictionary<int, int>();

    public void RunAlgm(int stIndex, IEnumerable<GraphEdge> edges)
    {
        Queue<int> queue = new Queue<int>();

        //GenRecord 
        List<Record> records = edges
            .GroupBy(e => e.stVertexId)
            .Select(g => g.First())
            .Select(e => new Record() { id = e.stVertexId })
            .ToList();
        //records = vertexs.Select(v => new Record() { id = v.id }).ToList();

        //ready 
        {
            var stRec = records.Where(r => r.id == stIndex).First();
            stRec.visited = true;
            stRec.dist = 0;
            queue.Append(stIndex);
        }

        //start
        int maxCount = 10000;
        while (true)
        {
            //IF BREAK
            maxCount--;
            if (maxCount < 0) break;
            if (queue.Count() == 0) break;

            //临时起点
            var tmpIndex = queue.Dequeue();
            var tmpEdges = edges.AtSt(tmpIndex); 
            var parentDist = records.Where(r => r.id == tmpIndex).First().dist;

            //
            foreach (var tmpEdge in tmpEdges)
            {
                int focusId = tmpEdge.edVertexId;

                var curRec = records.Where(r => r.id == focusId).First();
                if (curRec.visited == true) { continue; }
                queue.Append(focusId);

                curRec.visited = true;
                curRec.dist = parentDist + 1;
                curRec.parentId = tmpEdge.stVertexId;
            }
        } 
        _records = records;
        //dists = records.ToDictionary(r => r.id, r => r.dist);
        //paths = records.ToDictionary(r => r.id, r => r.path);

    }

    /// <summary>
    /// 获得路径
    /// </summary>
    /// <param name="stIndex"></param>
    /// <param name="edIndex"></param>
    /// <returns></returns>
    public IList<int> GetPathIds(int stIndex, int edIndex)
    {
        List<int> ids = new List<int>();

        var records = _records;
        ids.Add(edIndex);
        int count = records.Count + 3;
        while (count > 0)
        {
            count--;

            var edRecord = records.Where(r => r.id == edIndex).First();
            ids.Add(edRecord.parentId);
            if (stIndex == edRecord.parentId) { break; }
        }
        return ids;
    }



    internal struct Record
    {
        public Record()
        {
            this.id = 0;
            this.dist = double.MaxValue;
            this.visited = false;
            this.parentId = 0;
        } 
        public int id { get; set; }
        public double dist { get; set; } 
        public bool visited { get; set; } 
        public int parentId { get; set; }

    }

}


